package io.github.handyang.algorithms.digraph;

import com.google.common.collect.Lists;
import lombok.extern.slf4j.Slf4j;
import org.junit.Assert;
import org.junit.Test;

@Slf4j
public class DigraphTest {

    @Test
    public void testReverse() {
        ArrayDigraph digraph = new ArrayDigraph(4);
        digraph.addEdge(0, 1);
        digraph.addEdge(1, 2);
        digraph.addEdge(0, 3);

        Digraph reverse = digraph.reverse();

        Assert.assertEquals(Lists.newArrayList(0), Lists.newArrayList(reverse.adj(1)));
    }

    @Test
    public void testDirectedDFS() {
        Digraph graph = new ArrayDigraph(5);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(0, 3);
        graph.addEdge(0, 4);

        log.info("{}", graph);

        DirectedDFS dfs = new DirectedDFS(graph, 2);
        Assert.assertFalse(dfs.marked(0));

        dfs = new DirectedDFS(graph, 0);
        Assert.assertTrue(dfs.marked(2));
    }

    @Test
    public void testDirectedCycle() {
        Digraph graph = new ArrayDigraph(5);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(0, 3);
        graph.addEdge(0, 4);

        log.info("{}", graph);

        DirectedCycle directedCycle = new DirectedCycle(graph);
        Assert.assertFalse(directedCycle.hasCycle());

        graph = new ArrayDigraph(5);
        graph.addEdge(0, 1);
        graph.addEdge(1, 2);
        graph.addEdge(2, 1);
        graph.addEdge(0, 3);
        graph.addEdge(0, 4);

        log.info("{}", graph);

        directedCycle = new DirectedCycle(graph);
        Assert.assertTrue(directedCycle.hasCycle());
        Assert.assertEquals(Lists.newArrayList(2, 1, 0), directedCycle.cycle());
    }
}
